home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / DDJMAG / DDJ9006.ZIP / STEVENS.LST < prev    next >
File List  |  1990-05-02  |  19KB  |  676 lines
  1. _C PROGRAMMING COLUMN_
  2. by Al Stevens
  3.  
  4. [LISTING ONE]
  5.  
  6. /* ---------- hyprtree.h --------- */
  7.  
  8. #define NODELEN 256         /* length of a node   */
  9. #define MAXLEVELS 10        /* tree levels        */
  10. #define MAXKEYLENGTH 25     /* maximum key length */
  11.  
  12. #define TRUE 1
  13. #define FALSE !TRUE
  14.  
  15. #define KSPACE (NODELEN-sizeof(NODEHDR))
  16. #define HYPERTREE "hyprtree.ndx"
  17.  
  18. /* ----- computes length of a key in a node -------- */
  19. #define keylength(nd,kp) (strlen(kp) + 1 + \
  20.     ((nd).nodehdr.isleaf?sizeof(KEYVALUE):sizeof(NODEPOINTER)))
  21.  
  22. /* ---------- node pointers and key values ---------- */
  23. typedef long KEYVALUE;
  24. typedef int NODEPOINTER;
  25.  
  26. typedef union {
  27.     KEYVALUE keyvalue;
  28.     NODEPOINTER nodepointer;
  29. } KEYPOINTER;
  30.  
  31. /* ---------- header record for a hypertree ---------- */
  32. typedef struct {
  33.     NODEPOINTER rootnode;
  34. } TREEHDR;
  35.  
  36. /* ---- header structure for a hypertree node -------- */
  37. typedef struct  {
  38.     int isleaf;         /* true if the node is a leaf */
  39.     NODEPOINTER parent; /* node number of parent */
  40.     KEYPOINTER lower;   /* keys < this node (or value if leaf)*/
  41. } NODEHDR;
  42.  
  43. /* --------- node record for a hypertree ---------- */
  44. typedef struct {
  45.     NODEHDR nodehdr;
  46.     char keys[KSPACE];
  47. } TREENODE;
  48.  
  49. /* ------------- prototypes --------------- */
  50. void addkey(char *key, KEYVALUE keyvalue);
  51. int findkey(char *key);
  52. int firstkey(void);
  53. int lastkey(void);
  54. int nextkey(void);
  55. int prevkey(void);
  56. KEYVALUE current_keyvalue(void);
  57. char *current_keystring(void);
  58.  
  59.  
  60. [LISTING TWO]
  61.  
  62. /* ---------------- addkey.c -------------- */
  63.  
  64. #include <stdio.h>
  65. #include <stdlib.h>
  66. #include <string.h>
  67. #include "hyprtree.h"
  68.  
  69. static void addkeyentry(int level, char *key,
  70.                 KEYPOINTER keypointer, NODEPOINTER lowernode);
  71. static void nullnode(int level);
  72. static int freespace(TREENODE node);
  73. static void writenode(int level);
  74. static void adopt(NODEPOINTER child, NODEPOINTER parent);
  75.  
  76. static TREENODE *nodes[MAXLEVELS];
  77. static NODEPOINTER nodenbr[MAXLEVELS];
  78. static NODEPOINTER nextnode;
  79.  
  80. static FILE *htree;
  81. static TREEHDR th;
  82.  
  83. /*
  84.  *  Add a key string value and its associated KEYVALUE to
  85.  * the hypertree.
  86.  */
  87. void addkey(char *key, KEYVALUE keyvalue)
  88. {
  89.     KEYPOINTER keypointer;
  90.     if (key == NULL)    {
  91.         /* ------ terminal key, complete the tree ------ */
  92.         if (htree != NULL)  {
  93.             int level = 0;
  94.             /* -------- write the unwritten nodes -------- */
  95.             while (nodes[level] != NULL)    {
  96.                 writenode(level);
  97.                 free(nodes[level]);
  98.                 level++;
  99.             }
  100.             /* ------ update the header block ---------- */
  101.             th.rootnode = nodenbr[level-1];
  102.             fseek(htree, 0L, SEEK_SET);
  103.             fwrite(&th, sizeof(TREEHDR), 1, htree);
  104.  
  105.             fclose(htree);
  106.         }
  107.     }
  108.     else    {
  109.         keypointer.keyvalue = keyvalue;
  110.         if (strlen(key) <= MAXKEYLENGTH)
  111.             addkeyentry(0, key, keypointer, 0);
  112.     }
  113. }
  114.  
  115. static void addkeyentry(int level, char *key,
  116.                 KEYPOINTER keypointer, NODEPOINTER lowernode)
  117. {
  118.     char *kp;
  119.  
  120.     if (nodes[level] == NULL)   {
  121.         /* -------- build a new node ---------- */
  122.         if (level == 0) {
  123.             /* ------ building a new tree ------ */
  124.             htree = fopen(HYPERTREE, "wb+");
  125.             /* ----- write a NULL header for now ----- */
  126.             fwrite(&th, sizeof(TREEHDR), 1, htree);
  127.         }
  128.         if ((nodes[level] = malloc(sizeof(TREENODE))) == NULL)  {
  129.             fputs("\nOut of memory!", stderr);
  130.             exit(1);
  131.         }
  132.         nodes[level+1] = NULL;
  133.         nullnode(level);
  134.         /* ---- point to the node of the lower keys --- */
  135.         nodes[level]->nodehdr.lower.nodepointer = lowernode;
  136.         /* --- assign the next node number to this node --- */
  137.         nodenbr[level] = ++nextnode;
  138.     }
  139.     if (keylength(*nodes[level],key) >
  140.             freespace(*nodes[level]))   {
  141.         /* -------- this node is full -------- */
  142.         KEYPOINTER keyp;
  143.         NODEPOINTER lowernode;
  144.         /* ---- write the node to the index file ---- */
  145.         writenode(level);
  146.         /* ---- remember the node nbr at this level ---- */
  147.         lowernode = nodenbr[level];
  148.         /* --- assign a new node number to this level --- */
  149.         nodenbr[level] = ++nextnode;
  150.         /* --- grow or add to parent with the current key --- */
  151.         memset(&keyp, 0, sizeof(KEYPOINTER));
  152.         keyp.nodepointer = nodenbr[level];
  153.         addkeyentry(level+1, key, keyp, lowernode);
  154.         /* - now set the node at this level to NULL values - */
  155.         nullnode(level);
  156.         nodes[level]->nodehdr.lower = keypointer;
  157.     }
  158.     else    {
  159.         /* ------ insert the key into the node ------ */
  160.         kp = nodes[level]->keys;
  161.         /* ----- scan to the end of the node ----- */
  162.         while (*kp)
  163.             kp += keylength(*nodes[level], kp);
  164.         strcpy(kp, key);
  165.         /* ----- attach the key pointer to the key ----- */
  166.         kp += strlen(kp)+1;
  167.         if (level == 0)
  168.             *((KEYVALUE *)kp) = keypointer.keyvalue;
  169.         else
  170.             *((NODEPOINTER *)kp) = keypointer.nodepointer;
  171.     }
  172. }
  173.  
  174. /* --------- build a null node ------------ */
  175. static void nullnode(int level)
  176. {
  177.     memset(nodes[level], 0, NODELEN);
  178.     nodes[level]->nodehdr.isleaf = level == 0;
  179. }
  180.  
  181. /* ------ compute space remaining in a node ------- */
  182. static int freespace(TREENODE node)
  183. {
  184.     int sp = KSPACE;
  185.     char *kp = node.keys;
  186.  
  187.     while (*kp) {
  188.         sp -= keylength(node,kp);
  189.         kp += keylength(node,kp);
  190.     }
  191.     return sp;
  192. }
  193.  
  194. /* ------ write a completed node ------- */
  195. static void writenode(int level)
  196. {
  197.     long where = (nodenbr[level]-1)*NODELEN+sizeof(TREEHDR);
  198.  
  199.     fseek(htree, where, SEEK_SET);
  200.     fwrite(nodes[level], NODELEN, 1, htree);
  201.     if (level)  {
  202.         /* - this is a parent node, update its children - */
  203.         char *kp = nodes[level]->keys;
  204.         adopt(nodes[level]->nodehdr.lower.nodepointer,
  205.                     nodenbr[level]);
  206.         while (*kp) {
  207.             adopt(*((NODEPOINTER *)(kp+strlen(kp)+1)),
  208.                     nodenbr[level]);
  209.             kp += keylength(*nodes[level], kp);
  210.         }
  211.     }
  212. }
  213.  
  214. /* ---- write a parent node number into a child node ---- */
  215. static void adopt(NODEPOINTER child, NODEPOINTER parent)
  216. {
  217.     NODEHDR nodehdr;
  218.     long here = ftell(htree);
  219.     long where = (child-1)*NODELEN+sizeof(TREEHDR);
  220.  
  221.     fseek(htree, where, SEEK_SET);
  222.     fread(&nodehdr, sizeof(NODEHDR), 1, htree);
  223.     nodehdr.parent = parent;
  224.     fseek(htree, where, SEEK_SET);
  225.     fwrite(&nodehdr, sizeof(NODEHDR), 1, htree);
  226.     fseek(htree, here, SEEK_SET);
  227. }
  228.  
  229. [LISTING THREE]
  230.  
  231. /* ----------- srchtree.c ------------ */
  232.  
  233. #include <stdio.h>
  234. #include <stdlib.h>
  235. #include <string.h>
  236. #include "hyprtree.h"
  237.  
  238. /* ---------- search packet ----------- */
  239. typedef struct  {
  240.     NODEPOINTER node;
  241.     char *ky;
  242. } SEARCH;
  243.  
  244. FILE *htree;
  245. static TREEHDR th;
  246. static TREENODE node;
  247. static SEARCH current;
  248.  
  249. static void readnode(NODEPOINTER nodepointer);
  250. static void opentree(void);
  251.  
  252. /*
  253.  * Find a specified key in the tree.
  254.  * Return TRUE if found.
  255.  * Return FALSE if not found.
  256.  */
  257. int findkey(char *key)
  258. {
  259.     opentree();
  260.     if (th.rootnode)    {
  261.         SEARCH save = current;
  262.         readnode(th.rootnode);
  263.         while (TRUE)    {
  264.             int cmp;
  265.             current.ky = node.keys;
  266.             while (*current.ky) {
  267.                 cmp = stricmp(key, current.ky);
  268.                 if (cmp < 0)    {
  269.                     save = current;
  270.                     break;
  271.                 }
  272.                 if (cmp == 0)
  273.                     return TRUE;
  274.                 current.ky += keylength(node, current.ky);
  275.             }
  276.             if (!node.nodehdr.isleaf)   {
  277.                 if (current.ky == node.keys)
  278.                     readnode(node.nodehdr.lower.nodepointer);
  279.                 else
  280.                     readnode(*((NODEPOINTER *)
  281.                         (current.ky-sizeof(NODEPOINTER))));
  282.             }
  283.             else    {
  284.                 current = save;
  285.                 readnode(current.node);
  286.                 break;
  287.             }
  288.         }
  289.     }
  290.     return FALSE;
  291. }
  292.  
  293. /*
  294.  * Find the first sequential key in the tree.
  295.  * Return TRUE if found.
  296.  * Return FALSE if not found (the tree is empty).
  297.  */
  298. int firstkey(void)
  299. {
  300.     opentree();
  301.     if (th.rootnode)    {
  302.         readnode(th.rootnode);
  303.         while (!node.nodehdr.isleaf)
  304.             readnode(node.nodehdr.lower.nodepointer);
  305.         current.ky = node.keys;
  306.         return TRUE;
  307.     }
  308.     return FALSE;
  309. }
  310.  
  311. /*
  312.  * Find the last sequential key in the tree.
  313.  * Return TRUE if found.
  314.  * Return FALSE if not found (the tree is empty).
  315.  */
  316. int lastkey(void)
  317. {
  318.     NODEPOINTER np;
  319.     opentree();
  320.     if (th.rootnode)    {
  321.         int len = 0;
  322.         np = th.rootnode;
  323.         current.node = th.rootnode;
  324.         current.ky = node.keys;
  325.         do  {
  326.             SEARCH save = current;
  327.             readnode(np);
  328.             current.ky = node.keys;
  329.             while (*current.ky) {
  330.                 len = keylength(node, current.ky);
  331.                 current.ky += len;
  332.             }
  333.             if (current.ky == node.keys)    {
  334.                 readnode(save.node);
  335.                 current.ky = save.ky;
  336.                 break;
  337.             }
  338.             else
  339.                 np = *((NODEPOINTER *)
  340.                     (current.ky-sizeof(NODEPOINTER)));
  341.         } while (!node.nodehdr.isleaf);
  342.         current.ky -= len;
  343.         return TRUE;
  344.     }
  345.     return FALSE;
  346. }
  347.  
  348. /*
  349.  * Find the next sequential key in the tree.
  350.  * Return TRUE if found.
  351.  * Return FALSE if not found (the tree is empty or at the end).
  352.  */
  353. int nextkey(void)
  354. {
  355.     opentree();
  356.     if (th.rootnode)    {
  357.         if (current.ky == NULL)
  358.             return firstkey();
  359.         current.ky += keylength(node, current.ky);
  360.         if (!node.nodehdr.isleaf)   {
  361.             readnode(*((NODEPOINTER *)
  362.                     (current.ky-sizeof(NODEPOINTER))));
  363.             current.ky = node.keys;
  364.             while (!node.nodehdr.isleaf)
  365.                 readnode(node.nodehdr.lower.nodepointer);
  366.         }
  367.         /* ----- while at the end of a node ------ */
  368.         while (*current.ky == '\0') {
  369.             NODEPOINTER child = current.node;
  370.             if (node.nodehdr.parent == 0)
  371.                 break;
  372.             readnode(node.nodehdr.parent);
  373.             current.ky = node.keys;
  374.             if (child == node.nodehdr.lower.nodepointer)
  375.                 break;
  376.             while (*current.ky) {
  377.                 NODEPOINTER this = *((NODEPOINTER *)
  378.                     (current.ky+strlen(current.ky)+1));
  379.                 current.ky += keylength(node, current.ky);
  380.                 if (this == child)
  381.                     break;
  382.             }
  383.         }
  384.         return *current.ky != '\0';
  385.     }
  386.     return FALSE;
  387. }
  388.  
  389. /*
  390.  * Find the previous sequential key in the tree.
  391.  * Return TRUE if found.
  392.  * Return FALSE if not found
  393.  * (the tree is empty or at the beginning).
  394.  */
  395. int prevkey(void)
  396. {
  397.     char *kp;
  398.     opentree();
  399.     if (th.rootnode)    {
  400.         if (current.ky == NULL)
  401.             return lastkey();
  402.         if (!node.nodehdr.isleaf)   {
  403.             /* ----- navigate to end of the lower leaf ----- */
  404.             NODEPOINTER np;
  405.             if (current.ky == node.keys)
  406.                 np = node.nodehdr.lower.nodepointer;
  407.             else
  408.                 np = *((NODEPOINTER *)
  409.                     (current.ky-sizeof(NODEPOINTER)));
  410.             while (!node.nodehdr.isleaf)    {
  411.                 readnode(np);
  412.                 current.ky = node.keys;
  413.                 while (*current.ky)
  414.                     current.ky += keylength(node, current.ky);
  415.                 np = *((NODEPOINTER *)
  416.                     (current.ky-sizeof(NODEPOINTER)));
  417.             }
  418.         }
  419.         /* ----- while at the beginning of a node ------ */
  420.         while (current.ky == node.keys) {
  421.             NODEPOINTER child = current.node;
  422.             if (node.nodehdr.parent == 0)
  423.                 break;
  424.             readnode(node.nodehdr.parent);
  425.             current.ky = node.keys;
  426.             if (child == node.nodehdr.lower.nodepointer)
  427.                 continue;
  428.  
  429.             while (*current.ky) {
  430.                 NODEPOINTER this = *((NODEPOINTER *)
  431.                     (current.ky+strlen(current.ky)+1));
  432.                 current.ky += keylength(node, current.ky);
  433.                 if (this == child)
  434.                     break;
  435.             }
  436.         }
  437.         /* -------- go to previous key in node -------- */
  438.         if (current.ky != node.keys)    {
  439.             kp = node.keys;
  440.             while (kp+keylength(node, kp) < current.ky)
  441.                 kp += keylength(node, kp);
  442.             current.ky = kp;
  443.             return TRUE;
  444.         }
  445.     }
  446.     return FALSE;
  447. }
  448.  
  449. /*
  450.  * Return the key value associated with the most recently
  451.  * retrieved key.
  452.  */
  453. KEYVALUE current_keyvalue(void)
  454. {
  455.     KEYVALUE rtn;
  456.     if (!node.nodehdr.isleaf)   {
  457.         SEARCH save = current;
  458.         current.ky += keylength(node, current.ky);
  459.         while (!node.nodehdr.isleaf)    {
  460.             NODEPOINTER np;
  461.             if (current.ky == node.keys)
  462.                 np = node.nodehdr.lower.nodepointer;
  463.             else
  464.                 np = *((NODEPOINTER *)
  465.                     (current.ky-sizeof(NODEPOINTER)));
  466.             readnode(np);
  467.             current.ky = node.keys;
  468.         }
  469.         rtn = node.nodehdr.lower.keyvalue;
  470.         current = save;
  471.         readnode(save.node);
  472.         return rtn;
  473.     }
  474.     return *((KEYVALUE *)(current.ky+strlen(current.ky)+1));
  475. }
  476.  
  477. /*
  478.  * Return the key string value of the most recently
  479.  * retrieved key.
  480.  */
  481. char *current_keystring(void)
  482. {
  483.     return current.ky;
  484. }
  485.  
  486. /* -------- open the tree ----------- */
  487. static void opentree(void)
  488. {
  489.     if (htree == NULL)  {
  490.         if ((htree = fopen(HYPERTREE, "rb")) == NULL)   {
  491.             fputs("\n" HYPERTREE " not found", stderr);
  492.             exit(1);
  493.         }
  494.         fread(&th, sizeof(TREEHDR), 1, htree);
  495.     }
  496. }
  497.  
  498. /* ---------- read a specified node ------------- */
  499. static void readnode(NODEPOINTER nodepointer)
  500. {
  501.     long where = (nodepointer-1)*NODELEN+sizeof(TREEHDR);
  502.  
  503.     fseek(htree, where, SEEK_SET);
  504.     fread(&node, NODELEN, 1, htree);
  505.     current.node = nodepointer;
  506. }
  507.  
  508.  
  509.  
  510. [LISTING FOUR]
  511.  
  512. /* -------- keyextr.c ---------- */
  513.  
  514. /*
  515.  * Build a test HyperTree from standard input.
  516.  * <> delimiters define the key values.
  517.  * This is pass one, which builds the sortable table.
  518.  */
  519.  
  520. #include <stdio.h>
  521. #include <string.h>
  522. #include "hyprtree.h"
  523.  
  524. #define KEYTOKEN '<'
  525. #define TERMINAL '>'
  526. #define QUOTE    '"'
  527. #define ESCAPE   '\\'
  528.  
  529. void main(void)
  530. {
  531.     int c;
  532.     while ((c = getchar()) != EOF)  {
  533.         if (c == KEYTOKEN)  {
  534.             long fileposition = ftell(stdin)-1;
  535.             int counter = 0;
  536.             putchar(QUOTE);
  537.             while ((c = getchar()) != TERMINAL) {
  538.                 if (c == EOF || counter++ == MAXKEYLENGTH)
  539.                     break;
  540.                 if (c == QUOTE)
  541.                     putchar(ESCAPE);
  542.                 putchar(c);
  543.             }
  544.             putchar(QUOTE);
  545.             putchar(',');
  546.             printf("%ld\n", fileposition);
  547.         }
  548.     }
  549. }
  550.  
  551.  
  552.  
  553. [LISTING FIVE]
  554.  
  555. /* ----------- keybuild.c ----------- */
  556.  
  557. /*
  558.  * Build a test HyperTree from standard input.
  559.  * This is pass three, which builds the HyperTree
  560.  * from the sorted table.
  561.  */
  562.  
  563. #include <stdio.h>
  564. #include <string.h>
  565. #include <stdlib.h>
  566. #include "hyprtree.h"
  567.  
  568. #define QUOTE    '"'
  569. #define ESCAPE   '\\'
  570.  
  571. void main(void)
  572. {
  573.     int c;
  574.     char key[MAXKEYLENGTH+1];
  575.     char kv[20];
  576.     KEYVALUE keyvalue;
  577.  
  578.     while ((c = getchar()) != EOF)  {
  579.         if (c == QUOTE) {
  580.             int counter = 0;
  581.             char *cp = key;
  582.             while ((c = getchar()) != QUOTE)    {
  583.                 if (c == EOF || counter++ == MAXKEYLENGTH)
  584.                     break;
  585.                 if (c == ESCAPE)
  586.                     c = getchar();
  587.                 *cp++ = c;
  588.             }
  589.             *cp = '\0';
  590.             if (getchar() == ',')   {
  591.                 char *kp = kv;
  592.                 while ((c = getchar()) != '\n' && c != EOF)
  593.                     *kp++ = c;
  594.                 *kp = '\0';
  595.                 keyvalue = atol(kv);
  596.                 addkey(key, keyvalue);
  597.             }
  598.         }
  599.     }
  600.     addkey(NULL, keyvalue);
  601. }
  602.  
  603.  
  604.  
  605. [LISTING SIX]
  606.  
  607. /* ------------- hyprsrch.c -------------- */
  608.  
  609. /*
  610.  * Search the test HyperTree for a match on the
  611.  * command-line parameter.
  612.  * Display a screen of text starting at the
  613.  * position indicated for the matching (or closest)
  614.  * entry in the HyperTree.
  615.  */
  616.  
  617. #include <stdio.h>
  618. #include <string.h>
  619. #include <ctype.h>
  620. #include <conio.h>
  621. #include "hyprtree.h"
  622.  
  623. #define SCRLINES 25
  624.  
  625. void main(int argc, char *argv[])
  626. {
  627.     if (argc < 3)
  628.         fprintf(stderr, "Usage: hyprsrch textfile keyvalue");
  629.     else    {
  630.         int kb = 0;
  631.         FILE *fp = fopen(argv[1], "r");
  632.         if (fp == NULL) {
  633.             fprintf(stderr, "No such file as %s", argv[1]);
  634.             return;
  635.         }
  636.         findkey(argv[2]);
  637.         while (toupper(kb) != 'Q')  {
  638.             int lc = 4, c;
  639.             KEYVALUE kv = current_keyvalue();
  640.             printf("\n%s (%ld)", current_keystring(), kv);
  641.             printf("\n------------------------------------\n");
  642.             if (kv) {
  643.                 fseek(fp, kv, SEEK_SET);
  644.                 while ((c = getc(fp)) != EOF && lc < SCRLINES){
  645.                     if (c == '\n')
  646.                         lc++;
  647.                     putchar(c);
  648.                 }
  649.             }
  650.             printf("\nF = first, "
  651.                      "L = last, "
  652.                      "N = next, "
  653.                      "P = previous, "
  654.                      "Q = quit...");
  655.             kb = getch();
  656.             switch (toupper(kb))    {
  657.                 case 'F':
  658.                     firstkey();
  659.                     break;
  660.                 case 'L':
  661.                     lastkey();
  662.                     break;
  663.                 case 'N':
  664.                     nextkey();
  665.                     break;
  666.                 case 'P':
  667.                     prevkey();
  668.                     break;
  669.                 default:
  670.                     break;
  671.             }
  672.         }
  673.     }
  674. }
  675.  
  676.